Many coding schemes compress sample array data using a subdivision of the sample array into blocks. The sample array may define a spatial sampling of texture, i.e. pictures, but of course other sample arrays may be compressed using similar coding techniques, such as depth maps and the like. Owing to the different nature of the information spatially sampled by the respective sample array, different coding concepts are best suited for the different kinds of sample arrays. Irrespective of the kind of sample array, however, many of these coding concepts use block-subdivisioning in order to assign individual coding options to the blocks of the sample array, thereby finding a good tradeoff between side information rate for coding the coding parameters assigned to the individual blocks on the one hand and the residual coding rate for coding the prediction residual due to misprediction of the respective block, or finding a good comprise in rate/distortion sense, with or without residual coding.
Mostly, blocks are of rectangular or quadratic shape. Obviously, it would be favorable to be able to adapt the shape of the coding units (blocks) to the content of the sample array to be coded. Unfortunately, however, adapting the shape of the blocks or coding units to the sample array content involves spending additional side information for signaling the block partitioning. Wedgelet-type partitioning of blocks has been found to be an appropriate compromise between the possible block partitioning shapes, and the involved side information overhead. Wedgelet-type partitioning leads to a partitioning of the blocks into wedgelet partitions for which, for example, specific coding parameters may be used.